This invention relates to the field of multiprocessor computers with cache memories.
In recent years, great efforts have been expended to enable computers to operate at greater speeds. One method of accomplishing greater operating speeds for computers is through the use of cache memories Cache memories are random access memories (RAMS) that have faster operating speeds than main memories. In addition, cache memories are located closer to the processor, thereby enabling data to get from the cache memory to the processor more quickly than it can get from the main memory to the processor. In some implementations, there are more than one level of cache memory. One cache memory (referred to as primary cache) may reside on the processor chip, a second cache memory on another chip or chips on the same circuit board as the processor chip (referred to as secondary cache), with main memory on another circuit board or boards.
Cache memories do not contain the entire contents of main memory. Instead they contain the subset of main memory that is most likely to be used by the processor. If the processor requests a memory address not present in cache memory (referred to as a cache "miss"), the information in the requested memory address, and in other addresses nearby (referred to as a block), is brought into cache memory, and information currently present in cache memory is displaced.
Since cache memories contain only a subset of the main memory, a system must exist for recording which blocks of main memory currently reside in the cache and where in the cache memory they are stored. A number of such systems are well known in the art. These systems typically record the identity of the block in a table. Since the blocks are of a predetermined size, knowing one main memory address of a block and its position in the block (such as the first main memory address in the block), allows determination of whether a specific main memory address is present in the cache memory. A typical block size is 128 bytes.
There are two principal write policies for cache memories. According to the "write through" policy, when a processor changes data (i.e. the contents of a main memory address) and writes the new data back to the cache, it also writes the corresponding new data in main memory. According to the "write back" policy, a processor writes the new data back to main memory only when the data is displaced from the cache, when the new data is requested by another system component, or when the program has completed. Thus, a writeback system requires some method to determine when data in the cache is requested by another system component.
Another method for accomplishing greater processor speeds is to add more processors and split up the computing task among the various processors Typically, each of the processors has its own cache memory. This leads to the problem of cache coherency. Cache coherency means that all caches must have the same value for the contents of any given main memory address. To maintain cache coherency, most cache tables contain a method of indicating whether or not the information is known to be valid or not. This is commonly referred to as a "valid bit" If the valid bit contains one value (either 0 or 1), the processor can use the data immediately. If the valid bit contains the other value (1 or 0) the processor knows that the main memory address may have been changed, and therefore must request the current contents of that main memory address. There are a number of methods known in the art for determining whether the information in main memory addresses is valid or not.
In one common method, each processor module monitors all transactions on a system bus. Built into the processor module is logic which determines whether or not each transaction on the system bus requires that data that may be in the cache be declared invalid. If the processor module detects a transaction requiring data to be declared invalid, it issues an "invalidate request" to the various components of the processor module. The issuance and processing of invalidate requests will be explained in more detail in connection with the detailed description of the invention.
Since the address to be invalidated may not be in cache RAM (Random Access Memory) processing invalidate presents two problems. A significant amount of processor time may be spent attempting to perform invalidate requests on addresses that are not present in module cache. This processor time may take away from more useful processor activity. Second, invalidate requests for addresses that are not present in cache RAMS may occupy significant amounts of bandwidth on the module bus. Thus it is desirable to filter invalidate requests such that only invalidate requests for addresses that are present in the cache rams are broadcast over the module bus and are processed by the processor.
One method of filtering invalidate requests is taught in U.S. patent Application Ser. No. 07/212,416, filed Jun. 27, 1988 by Durdan, et al, entitled "Method and Apparatus for Filtering Invalidate Requests" now U.S. Pat. No. 5,058,006 and assigned to the assignee of the present application. In Durdan et al, a technique is disclosed wherein a dedicated data path is provided between the memory interface and the cache controller logic. This dedicated path is referred to as an invalidate bus or I-bus and this bus, along with the processor bus is considered as part of the memory interface. When a write transaction (the transaction that generates an invalidate request) is detected, the memory interface communicates with the cache controller via the I-bus in order to determine whether the write transaction involves a memory location copied in the cache memory hierarchy of the CPU module. If the written location is not present anywhere in the cache memory of the CPU, the write transaction is ignored, and no invalidate is forwarded to the cache controller or CPU, and the processor bus remains available for use by the CPU. If the written location is copied in the cache memory of the CPU module, the memory interface broadcasts the write transaction information over the processor bus, where it is received by the cache controller, and the CPU to be processed as an invalidate.
An element of Durdan, et al is a FIFO (first-in-first-out) queue called an invalidate Queue. The invalidate queue is placed between the system bus and the CPU module. The CPU monitors the system bus for write transactions on the system bus. When any data write transactions is detected on the system bus, the address of that transaction is placed on one end of the CPU module's Invalidate Queue and the valid bit is set. When the CPU is able to process an invalidate , the first valid entry is removed from the other end of the Invalidate Queue and its valid bit is cleared. The address of the write transaction is checked against the contents of the cache structure, and if present, the entry corresponding to that address is marked as invalid.
U.S. patent Application Ser. No. 07/212,347, filed Jun. 27, 1988 by Callander et al filed under the title "Multi-processor Computer System Having Shared Memory and Private Cache Memories" and subsequently retitled by amendment to "Circuit and Method of Serializing Transactions in a Multi-processor Computer System" and assigned to the assignee of the present application, discloses a method of synchronizing entries in an invalidate queue and a read data queue. FIG. 2 of Callander et al shows an invalidate queue placed between a system bus interface and a CPU bus interface.
U.S. patent application Ser. No. 07/547,850 filed Jun. 29, 1990, by Chisvin et al, entitled "Combined Queue for Invalidates and Return Data in Multiprocessor System", and assigned to the assignee of the present application, discloses an invalidate queue on the interface unit.
U.S. Pat. 4,142,234, issued Feb. 27, 1979 to Bean et al, and entitled "Bias Filter Memory for Filtering Out Unnecessary Interrogations of Cache Directories in a Multiprocessor System" discloses a cache control circuit that comprises a cache directory and controls, and a Buffer Invalidate Address Stack (BIAS) and further discloses a filter memory. FIG. 1 of Bean shows the BIAS array totally contained by the cache control circuit. The filter memory records the most recent cache block address(es) that have been passed to the Buffer Invalidate Address Stack (BIAS) for interrogating the associated cache directory. Subsequent addresses remotely provided from another processor or channel that would interrogate the same cache block address are "filtered out" by not being passed to the associated BIAS. Remote processor stores, and local and remote channel stores are inputted and compared against address(es) in the filter memory . If not equal to any valid address, in the filter memory, the inputted address is recorded as a valid entry in the filter memory, and it is gated into BIAS. If equal to any valid address, the inputted address is not entered into the filter memory, and it is not gated to BIAS, so the no cache interrogation results.
U.S. Pat. No. 4,195,340, issued Mar. 25, 1980 to Joyce et al, and entitled "First In First Out Activity Queue for a Cache Store" discloses a FIFO buffer. FIG. 2 of Joyce shows the FIFO buffer as totally contained by a Replacement and Update unit. The FIFO buffer is shown as receiving data from three separate receivers, the three receivers shown as totally contained by a Bus Interface Unit.